package 滑动窗口;


import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485141&idx=1&sn=0e4583ad935e76e9a3f6793792e60734&scene=21#wechat_redirect
 *
 * 示例 1:
 *
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 *
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 *
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 */
public class _3_无重复字符的最长子串 {

    public static void main(String[] args) {
        String s = "abcabcbb";
        _3_无重复字符的最长子串 _3_无重复字符的最长子串 = new _3_无重复字符的最长子串();
        int result = _3_无重复字符的最长子串.lengthOfLongestSubstring(s);
        System.out.println("result:" + result);
    }

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();

        int left = 0;
        int right = 0;

        int res = 0; // 记录结果
        while (right < s.length()) {
            Character c = s.charAt(right);
            right++;
            // 进行扩容内的内容更新
            map.put(c, map.getOrDefault(c, 0) + 1);

            while (map.get(c) > 1) {
                Character d = s.charAt(left);
                left++;
                map.put(d, map.get(d) - 1);
            }

            res = Math.max(right - left, res);
        }

        return res;
    }
}
